Các công cụ chế tác bằng đá tìm được ở Zemun cho thấy các cộng đồng săn bắn hái lượm đã sinh sống ở khu vực quanh Beograd ngày nay từ thời đại đồ đá cũ và đồ đá giữa. Một số công cụ thuộc về nền văn hóa Moustier của người Neanderthal. Các mảnh xương và hộp sọ của người Neanderthal thuộc thời kỳ đồ đá cũ được phát hiện trong một mỏ đá gần Leštane, trong một hang động ở Čukarica và gần chợ Skadarli. Những phát hiện các công cụ thuộc nền văn hóa Gravette và Aurignac cũng cho thấy con người đã định cư tại đây từ 50.000 đến 20.000 năm trước.[4]

Nền văn hóa thời đại đồ đá mới Starčevo và Vinča đã phát triển quanh Beograd và bao trùm cả bán đảo Balkan (cũng như một phần Trung Âu và Tiểu Á) khoảng 7.000 năm trước.[1][5][6]

Các di chỉ thời kỳ đồ đá sớm được phát hiện ở Vinča, Žarkovo và Phố Trên (tiếng Serbia: Горњем граду, thuộc khu thành cổ), phía trên cửa sông Sava đổ vào sông Danube. Như vậy, Beograd đã được định cư và gia tăng dân số liên tục. Nhiều nhà cửa đường phố ngày nay xếp chồng lên các tầng văn hóa tiền sử xa xưa.

Những nhóm người sinh sống và canh tác đầu tiên trên mảnh đất này có liên quan đến văn hóa cổ đại thời kỳ đồ đá mới, phát triển rực rỡ từ 6.200 đến 5.200 năm trước.[7] Các di chỉ nền văn hóa Starčevo được phát hiện và khai quật ở Beograd và vùng phụ cận, chủ yếu từ thị trấn Starčevo, địa danh được gán thành tên cho nền văn hóa này. Văn hóa Vinča (5.500-4.500 TCN) đã kế thừa văn hóa Starčevo, tiếp tục phát triển thành một nền văn hóa nông nghiệp tiên tiến hơn, cũng được đặt tên theo Vinča-Belo Brdo của Beograd. Di chỉ văn hóa Vinča cho thấy các cộng đồng rất lớn, có thể nói là lớn nhất châu Âu thời tiền sử;[8] các di sản tiêu biểu như tượng người phụ nữ Vinča; dấu vết đúc đồng sớm nhất tại châu Âu;[9] và chữ viết Vinča - một dạng ký tự sơ khai trước cả văn hóa Sumer và Minos.[10]

Đồi Vinča - Belo gần Beograd là khu khảo cổ quan trọng nhất về thời kỳ tiền sử ở châu Âu. Các cuộc khai quật tại cầu Rospi, Phố Trên, Karaburma, Zemun và Vinča khẳng định giả thuyết trước đây Beograd đã tập trung đông dân cư, phát triển mạnh nông nghiệp và các hoạt động trao đổi buôn bán khác. Các ngôi mộ táng thời đại đồ đồng kèm theo vật dụng kim loại được khai quật phát hiện là bằng chứng về sự giao thoa ảnh hưởng của các nền văn hóa khác nhau.